//
//  main.c
//  C_Study
//
//  Created by rui on 12-6-30.
//  Copyright (c) 2012年 Wang Rui. All rights reserved.
//

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <assert.h>
#include <unistd.h> 

/*
 @要点：链表
 */

typedef unsigned int bool;
#define true 1;
#define false 0;

#undef DEBUG
#define DEBUG 1

typedef struct Node {
	struct Node *pNext;
	struct Node	*pPrev;
	int data;
}NODE,*PNODE;


bool is_empty(PNODE pHead)
{
	assert(NULL != pHead);
	return (pHead->pNext == NULL);
}

int list_length(PNODE pHead)
{
	assert(NULL != pHead);
	PNODE p = pHead->pNext;
	
	int i = 0;
	while (p != NULL) {
		p = p->pNext;
		i++;
	}
	return i;
}

PNODE creat_list(int len)
{
	PNODE pHead = NULL;
	PNODE pTail = NULL;
	
	pHead = (PNODE)malloc(sizeof(NODE));
	pHead->pNext = NULL;
	pTail = pHead;
	
	//head node.(different from first node)
	if (pHead == NULL) 
	{
		printf("malloc failed!\n");
		exit(0);
	}
	
	int val;
	printf("Input Value:\n");
	
	for (int i=0; i<len; i++)
	{
		PNODE pNew = (PNODE)malloc(sizeof(NODE));
		if (NULL == pNew)
		{
			printf("malloc failed!\n");
			exit(0);
		}
		
		scanf("%d",&val);
		
		pNew->data = val;
		pNew->pNext = NULL;
		pTail->pNext = pNew;
		pTail = pNew;
	}
	
	return pHead;
}

void travel_list(PNODE pHead)
{
	assert(NULL != pHead);
	PNODE p = pHead->pNext; //fisrt node
	while (p != NULL) {
		printf("%d ",p->data);
		p = p->pNext;
	}
	printf("\n");
}

bool insert_list(PNODE pHead,int pos,int val)
{
	assert(NULL != pHead);
	PNODE p = pHead;
	
	
	int i = 0;                               //********************************************
	while (p != NULL && i<pos-1) {           //
		p = p->pNext;                        //使用此段代码可以不用判断链表的长度，是一个很好的算法
		i++;						         //
	}								         //当pos小于1时，循环不执行，if中判断成立，返回false
									         //
	if (p == NULL || i>pos-1) {              //pos小于等于（长度+1）时，p最多指向第长度个，
		printf("insert beyond bounds!\n");   //
		return false;						 //********************************************
	}										 
		
	
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	if (pNew == NULL) {
		printf("malloc failed!\n");
		exit(0);
	}

	PNODE temp = p->pNext;
	p->pNext = pNew;
	pNew->data = val;
	pNew->pNext = temp;
	
	return true;
}

bool delete_list(PNODE pHead,int pos,int *delVal)
{
	assert(NULL != pHead);
	PNODE p = pHead;
	
	int i = 0;
	while (p->pNext!= NULL && i<pos-1) {//既做边界判断，又确保p指向第pos-1个
		p = p->pNext;
		i++;
	}
	if ( p->pNext == NULL || i>pos-1) {
		printf("delete beyond bounds!\n");
		return false;
	}
	
	PNODE temp = p->pNext;
	*delVal = temp->data;
	p->pNext = temp->pNext;
	free(temp);
	temp = NULL;
	
	return true;	
}

void sort_list(PNODE pHead)
{
	assert(NULL != pHead);
	
	PNODE p,q;
	
	//选择排序
	for (p = pHead->pNext; p != NULL; p = p->pNext) {
		for (q = p->pNext; q != NULL; q = q->pNext) {
			if (p->data > q->data) {
				int t = p->data;
				p->data = q->data;
				q->data = t;
			}
		}
	}
}

/**********************************
 *@ main函数
 **********************************/
int main(int argc, const char * argv[])
{
	PNODE pHead = NULL;
	
	pHead = creat_list(5);
	travel_list(pHead);
	
	int val;
	if(delete_list(pHead, 1, &val))
	{
		printf("successed! delval:%d\n",val);
		travel_list(pHead);
	}
	else {
		printf("failed!\n");
	}
	
	return 0;
}

